#include "../bst/bst.h"

#define Balanced(x) (stature((x).lc) == stature((x).rc))
#define BalFac(x) (stature((x).lc) - stature((x).rc))
#define AvlBanlanced(x) ((-2 < stature(x)) && (stature(x) < 2))

template <typename T>
class AVL : public BST<T>
{
private:
    BinNodePosi(T) _insert(BinNodePosi(T) & node, const T &e);
    BinNodePosi(T) _remove(BinNodePosi(T) & node, const T &e);
    BinNodePosi(T) _r(BinNodePosi(T) & node);
    BinNodePosi(T) _l(BinNodePosi(T) & node);
    BinNodePosi(T) _lr(BinNodePosi(T) & node);
    BinNodePosi(T) _rl(BinNodePosi(T) & node);

public:
    BinNodePosi(T) insert(const T &e);
    bool remove(const T &e);
};

template <typename T>
BinNodePosi(T) AVL<T>::_r(BinNodePosi(T) & node)
{
    BinNodePosi(T) &lc = node->lc;
    node->lc = lc->rc;
    lc->rc = node;
    updateHeight(node);
    updateHeight(lc);
    return lc;
}

template <typename T>
BinNodePosi(T) AVL<T>::_l(BinNodePosi(T) & node)
{
    BinNodePosi(T) &rc = node->rc;
    node->rc = rc->lc;
    rc->lc = node;
    updateHeight(node);
    updateHeight(rc);
    return rc;
}

template <typename T>
BinNodePosi(T) AVL<T>::_lr(BinNodePosi(T) & node)
{
    node->lc = _l(node->lc);
    return _r(node);
}

template <typename T>
BinNodePosi(T) AVL<T>::_rl(BinNodePosi(T) & node)
{
    node->rc = _r(node->rc);
    return _l(node);
}

template <typename T>
BinNodePosi(T) AVL<T>::_insert(BinNodePosi(T) & node, const T &e)
{
    if (node == NULL)
        node = new BinNode<T>(e, NULL);
    else if (e < node->data)
    { // 插入到左子树
        node->lc = _insert(node->lc, e);
        if (!AvlBanlanced(node))
        {
            if (e < node->lc->data)
                node = _r(node); // 插入位置为ll 右旋保持平衡
            else
                node = _lr(node); // 插入位置为lr 先左旋后右旋保持平衡
        }
    }
    else if (e > node->data)
    { // 插入到右子树
        node->rc = _insert(node->rc, e);
        if (!AvlBanlanced)
        {
            if (e > node->rc->data)
                node = _l(node); // 插入位置为rr 左旋保持平衡
            else
                node = _rl(node); // 插入位置为rl 先右旋后左旋保持平衡
        }
    }

    return node;
}

template <typename T>
BinNodePosi(T) AVL<T>::_remove(BinNodePosi(T) & node, const T &e)
{
    if (node == NULL)
        return NULL;

    if (e < node->data)
    {
        node->lc = _remove(node->lc, e);
        if (!AvlBanlanced(node))
        {
            BinNodePosi(T) &r = node->rc;
            if (stature(r->rc) > stature(r->lc))
                node = _l(node); // 破坏平衡的节点位于rr 左旋保持平衡
            else
                node = _rl(node); // 破坏平衡的节点位于rl
        }
    }
    else if (e > node->data)
    {
        node->rc = _insert(node->rc, e);
        if (!AvlBanlanced(node))
        {
            BinNodePosi(T) &l = node->lc;
            if (stature(l->lc) > stature(l->rc))
                node = _r(node); // 破坏平衡的节点位于ll 右旋保持平衡
            else
                node = _lr(node); // 破坏平衡的节点位于lr
        }
    }
    else
    {
        if (node->lc != NULL && node->rc != NULL)
        {
            if (stature(node->lc) > stature(node->rc))
            {
                BinNodePosi(T) &p = node.lc;
                while (p != NULL)
                    p = p->rc; // 找到左子树中的最大节点
                node->data = p->data;
                node->lc = _remove(node->lc, p->data);
            }
            else
            {
                BinNodePosi(T) &p = node.rc;
                while (p != NULL)
                    p = p->lc; // 找到右子树中的最小节点
                node->data = p->data;
                node->rc = _remove(node->rc, p->data);
            }
        }
        else
        {
            BinNodePosi(T) &tmp = node;
            node = node->lc != NULL ? node->lc : node->rc;
            delete tmp;
        }
    }

    return node;
}

/**
 * 插入数据到avl树中, 并保持二叉树的平衡
 * @param  { BinNodePosi(T)& } e
 * @return { BinNodePosi(T)  }
 */
template <typename T>
BinNodePosi(T) AVL<T>::insert(const T &e)
{
    // BinNodePosi(T) & x = search(e);
    // if (x) return x; // 存在该节点就不必再插入该数据
    // x = new BinNode<T>(e, _hot);
    // _size++;
    return _insert(_root, e);
}

/**
 * 从avl树中删除数据, 并保持二叉树的平衡
 * @param  { BinNodePosi(T)& } e
 * @return { bool }
 */
template <typename T>
BinNodePosi(T) AVL<T>::remove(const T &e)
{
}
